class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param CityMap int整型vector<vector<>> 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    int dist[15][15]={0};
    int cnt[15][15]={0};
    int x1,y1,x2,y2;
    int dx[4]={-1,1,0,0};
    int dy[4]={0,0,-1,1};
    

    void bfs(vector<vector<int> >& CityMap,int n,int m)
    {
        memset(dist,-1,sizeof dist);
        dist[x1][y1]=0;
        cnt[x1][y1]=1;
        queue<pair<int,int>> q;
        q.push({x1,y1});
        while(q.size())
        {
            auto [a,b]=q.front();
            for(int k=0;k<4;k++)
            {
                int x=a+dx[k],y=b+dy[k];
                if(x>=0 &&x<n && y>=0 &&y<m &&CityMap[x][y]!=-1)
                {
                    if(dist[x][y]==-1)//第一次到达可以更新最近距离
                    {
                        dist[x][y]=dist[a][b]+1;
                        cnt[x][y]+=cnt[a][b];
                        q.push({x,y});
                    }
                    else if(dist[a][b]+1==dist[x][y]){//不是第一次到达
                        cnt[x][y]+=cnt[a][b];
                    }
                }
            }
            q.pop();
        }
    }
    int countPath(vector<vector<int> >& CityMap, int n, int m) {
        // write code here
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(CityMap[i][j]==1)
                {
                    x1=i,y1=j;
                }
                else if(CityMap[i][j]==2)
                {
                    x2=i,y2=j;
                }
            }
        }
        bfs(CityMap,n,m);
        return cnt[x2][y2];

    }
};